编译原理(6) |
您所在的位置:网站首页 › 编译原理 有限自动机 › 编译原理(6) |
3型文法:
3型文法也称正则文法 如果文法G=(N,Σ,P,S)的规则集P中所有规则满足A->Bx,或A->x,其中,A,B∈N,x∈Σ,则称3型文法。 如上所示,规则右部的非终结符号(如果有的话)出现在最左边,所以称为左线性正则文法,若为A->xB,则为右线性文法 有限自动机: 有限自动机分为确定性有限自动机(DFA)和不确定性有限自动机 DFA:M是一个五元组,M=(Σ,Q,δ,q0,F),其中Σ是输入符号的有穷集合;q0∈Q是初始状态;F是终止状态集合,F⊆Q; δ是Q与Σ直积到Q(下一个状态)的映射,也称状态转移函数
DFA原理:处在状态q∈Q中的有限控制器从左到右依次从输入带上读入字符,开始时有限状态控制器处在状态q0, 输入头指向Σ*中一个链的最左符号。映射δ(q,a)=q1(q,q1∈Q,a∈Σ)表示在状态q时,若输入符号为a,则 自动机M进入状态q1并且将输入头向右移动一个字符。 DFA接受的语言:如果一个句子x对于有限自动机M有δ(q0,x)=p,p∈F,那么称句子x被M接受。被M接受的句子的全集 称为M定义的语言,或称M所接受的语言,记作T(M)。T(M)={x|δ(q0,x)∈F} NFA: NFA和DFA的重要区别是:在NFA中δ(q,a)是一个状态集合,而在DFA中δ(q,a)是一个状态。 对于NFA M的映射:δ(q,a)={q1,q2,…,qk},k≥1,即M在状态q时接受输入字符a,可以选择状态集q1,q2,…,qk 中的任何一个状态作为下一个状态。 正则文法与有限自动机的关系: 1、若G=(VN,VT,P,S)是一个正则文法,则存在一个FA M=(Σ,Q,δ,q0,F),使得T(M)=L(G)。 由给定正则文法G=(VN,VT,P,S)构造FA M步骤:(1)、令Σ=VT,Q=VN∪{T},q0=S,其中T是一个新增的非终结符; (2)、如果在P中有产生式S->ε,则F={S,T},否则F={T}; (3)、如果在P中有产生式B->a,B∈VN,a∈VT,则T∈δ(B,a); (4)、如果在P中有产生式B->aC,B,C∈VN,a∈VT,则C∈δ(B,a); (5)、对于每一个a∈VT,有δ(T,a)=∅。 例子:给定正则文法G=(VN,VT,P,S),构造与G等价的NFA,其中,VN={S,A}, VT={0,1} P:S->0 A A->1 S A->0 (1)、设NFA M=(Σ,Q,δ,q0,F),根据上述构造步骤有: Σ=VT={0,1},Q=VN∪{T}={S,A,T},q0=S,F={T} (2)、映射δ为: δ(S,0)={A} (因为有规则S->0 A) δ(S,1)=∅ δ(A,0)={T} (因为有规则A->0) δ(A,1)={S} (因为有规则A->1 S) δ(T,0)=∅ δ(T,1)=∅
2、若 M=(Σ,Q,δ,q0,F)是一个有限自动机,则存在一个正则文法G=(VN,VT,P,S),使得L(G)=T(M) 由FA M构造G的一般步骤为:(1)、令VN=Q,VT=Σ,S=q0; (2)、如果C∈δ(B,a),B,C∈Q,a∈Σ,则在P中有产生式B->aC; (3)、如果C∈δ(B,a),C∈F,则在P中有产生式B->a。
特此记录有限自动机与正则文法相互转化的规则,以防遗忘。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |